package day3;

import java.util.*;

public class Main2 {
    /**
     * MT3 拜访
     * https://www.nowcoder.com/practice/491828fc7d93459db450b344c2aaaeef?tpId=128&tqId=33770&ru=/exam/oj
     */
    public int nn,mm;
    public int x1,y1;
    public int x2,y2;
    public int[][] visit = new int[11][11];
    public int[][] cnt = new int[11][11];

    public int countPath (int[][] CityMap, int n, int m) {
        // 要求最短的路径有多少个，因为涉及到最短路径问题，那么使用 bfs 进行解决
        nn = n;
        mm = m;
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                // 将所有的 visit 初始化为-1，表示为没有到过
                visit[i][j] = -1;
                if(CityMap[i][j] == 1) {
                    x1 = i;
                    y1 = j;
                }
                if(CityMap[i][j] == 2) {
                    x2 = i;
                    y2 = j;
                }
            }
        }

        return bfs(CityMap);
    }

    public int[] dx = {0,0,1,-1};
    public int[] dy = {1,-1,0,0};

    public int bfs(int[][] CityMap) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x1,y1});
        visit[x1][y1] = 0; // 用来记录某个位置是否到达过，并且到达这个位置的步数路径，根据这个进行选取最短路径
        cnt[x1][y1] = 1; // 用来记录到达某个位置，所存在的路径个数，也就是最短路径的个数

        while(!queue.isEmpty()) {
            int[] t = queue.poll();
            int a = t[0];
            int b = t[1];
            for(int k = 0;k < 4;k++) {
                int x = a + dx[k];
                int y = b + dy[k];
                if(x >= 0 && x < nn && y >= 0 && y < mm && CityMap[x][y] != -1) {
                    // 判断是否是第一次到达这个位置
                    if(visit[x][y] == -1) {
                        // 第一次，进行更新
                        visit[x][y] = visit[a][b] + 1;
                        cnt[x][y] += cnt[a][b];
                        queue.add(new int[]{x,y});
                    }else {
                        // 不是第一次到达，那么第一次到达这个位置的路径长度一定是最小的
                        // 当再次到达这个位置的时候，如果和第一个到达的路径长度一致，那么就是另一种最短方案
                        if(visit[x][y] == visit[a][b] + 1) {
                            //是最短路径，将其更新进入路径统计中
                            cnt[x][y] += cnt[a][b];
                        }
                    }
                }
            }
        }
        return cnt[x2][y2];
    }
}
